#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
typedef int Vertex; /* 顶点编号类型 */
typedef int GElemSet; /* 边权重类型 */
typedef char VertInfo; /* 顶点信息类型 */
typedef struct MGraphNode *MGraph; /* 邻接矩阵表示的图 */
struct MGraphNode {
    int n_verts; /* 顶点数 */
    int m_edges; /* 边数 */
    GElemSet **edge_matrix;/* 邻接矩阵 */
    VertInfo *ver_list; /* 存储顶点信息 */
    GElemSet no_edge_value; /* 表述没有边时的权重值 */
    bool directed; /* true为有向图，false为无向图 */
};
#define NIL -1      /* 顶点不存在时的返回值 */
#define kMaxV 100   /* 最多顶点数 */
#define kMaxNum 1e9 /* 大于最大距离值的数字 */

void InitGraph(MGraph graph, int kMaxVertex, GElemSet no_edge_value,
               bool directed);
bool ExistEdge(MGraph graph, Vertex u, Vertex v);
void InsertEdge(MGraph graph, Vertex u, Vertex v, GElemSet weight);
MGraph BuildGraph();

#define ErrorCode -1
Vertex parent[kMaxV];
/* 算法8-4：求最小生成树的Prim算法 Prim(graph) */
GElemSet Prim(MGraph graph) {
    int n, dist[kMaxV], min_dist, count_v;
    Vertex u, v;
    GElemSet total_weight;

    n = graph->n_verts;
    dist[0] = 0; /* dist[v]记录v到U的距离；首先默认根结点在集合U里 */
    for (v = 0; v < n; v++) {
        parent[v] = 0; /* 初始化所有顶点的父结点都是根结点0 */
        dist[v] = graph->edge_matrix[0][v]; /* 当前其它顶点v到U的距离就是(0,v)边长 */
    }
    parent[0] = NIL; /* 默认0是最小生成树的根结点，没有父结点 */
    total_weight = 0; /* 累计最小生成树的权重和 */
    count_v = 1; /* 累计当前收入最小生成树的顶点数 */
    while (true) {
        min_dist = graph->no_edge_value;
        for (v = 1; v < n; v++) { /* 找连通U和V-U的最短边 */
            if (dist[v] > 0 && dist[v] < min_dist) { /* 若v不在U内，且距离U更近 */
                min_dist = dist[v];
                u = v;
            }
        }
        if (min_dist < graph->no_edge_value) { /* 如果找到最小边对应的u */
            total_weight += dist[u];
            dist[u] = 0; /* 将u收入U */
            count_v++;
            for (v = 1; v < n; v++) { /* 更新u的邻接点v到U的距离 */
                if (dist[v] > 0 && graph->edge_matrix[u][v] != graph->no_edge_value) {
                    if (graph->edge_matrix[u][v] <
                            dist[v]) { /* 若收入u使得v到U的距离变小 */
                        dist[v] = graph->edge_matrix[u][v];
                        parent[v] = u; /* 更新树 */
                    }
                }
            }
        } else { /* 如果找不到V-U中的最小边了 */
            break; /* 结束循环 */
        }
    }
    if (count_v < n) {
        total_weight = ErrorCode; /* 最小生成树不存在 */
    }
    return total_weight;
}
/* 算法8-4 结束 */

int main(void) {
    MGraph graph;
    Vertex u;

    graph = BuildGraph();
    printf("total weight = %d\n", Prim(graph));
    for (u = 0; u < graph->n_verts; u++) {
        printf("%d ", parent[u]);
    }
    printf("\n");
    return 0;
}

void InitGraph(MGraph graph, int kMaxVertex, GElemSet no_edge_value,
               bool directed) {
    /* 初始化一个空的图 */
    GElemSet *array;
    int i;
    Vertex u, v;

    graph->n_verts = 0;
    graph->m_edges = 0;
    /* 声明二维数组graph->edge_matrix[kMaxVertex][kMaxVertex] */
    array = (GElemSet *)malloc(sizeof(GElemSet) * kMaxVertex * kMaxVertex);
    graph->edge_matrix = (GElemSet **)malloc(sizeof(GElemSet *) * kMaxVertex);
    for (i = 0; i < kMaxVertex; i++) {
        graph->edge_matrix[i] = &array[i * kMaxVertex];
    }
    /* 声明顶点信息数组graph->ver_list[kMaxVertex] */
    graph->ver_list = (VertInfo *)malloc(sizeof(VertInfo) * kMaxVertex);
    graph->no_edge_value = no_edge_value;
    graph->directed = directed;
    for (u = 0; u < kMaxVertex; u++) {
        for (v = 0; v < kMaxVertex; v++) {
            graph->edge_matrix[u][v] = graph->no_edge_value;
        }
        graph->edge_matrix[u][u] =
            0; /* 最短路问题中假设原地不动距离为0 */
    }
}

bool ExistEdge(MGraph graph, Vertex u, Vertex v) {
    bool ret = false;

    if (u < graph->n_verts && v < graph->n_verts) {
        if (u != v && graph->edge_matrix[u][v] != graph->no_edge_value) {
            ret = true;
        }
    }
    return ret;
}

void InsertEdge(MGraph graph, Vertex u, Vertex v, GElemSet weight) {
    if (ExistEdge(graph, u, v) == false) {
        graph->edge_matrix[u][v] = weight;
        graph->m_edges++;
        if (graph->directed == false) {
            graph->edge_matrix[v][u] = weight;
        }
    }
}

MGraph BuildGraph() {
    MGraph graph;
    int n, m, i;
    Vertex u, v;
    GElemSet weight;

    graph = (MGraph)malloc(sizeof(struct MGraphNode));
    InitGraph(graph, kMaxV, kMaxNum, false);
    scanf("%d %d\n", &n, &m);
    graph->n_verts = n;
    for (i = 0; i < m; i++) {
        scanf("%d %d %d\n", &u, &v, &weight);
        InsertEdge(graph, u, v, weight);
    }
    return graph;
}